最优化方法 - 凸集
最优化方法 - 凸集
凸集的定义、性质
设\(S \subseteq E^n\)，若对\(\forall x^{(1)}, x^{(2)} \in S\)及\(\forall \lambda \in [0, 1]\)，都有\(\lambda x^{(1)} + (1 - \lambda) x^{(2)} \in S\)，则称\(S\)为凸集。
设\(S_1\)和\(S_2\)是两个凸集，\(\beta\)实数，则
\(\beta S_1 = \{ \beta x \mid x \in S_1 \}\)是凸集
\(S_1 + S_2 = \{ x^{(1)} + x^{(2)} \mid x^{(1)} \in S_1, x^{(2)} \in S_2 \}\)是凸集
\(S_1 - S_2 = \{ x^{(1)} - x^{(2)} \mid x^{(1)} \in S_1, x^{(2)} \in S_2 \}\)是凸集
\(S_1 \bigcap S_2\)是凸集
极点和极方向的定义
极点
设\(S\)是非空集合，\(x \in S\)，若\(x\)不能表示成\(S\)中两个不同点的凸组合，即若假设\(x = \lambda x^{(1)} + (1 - \lambda)x^{(2)}\)，必推出\(x = x^{(1)} = x^{(2)}\)，则称\(x\)是凸集\(S\)的极点。
方向
设\(S\)是闭凸集，\(d\)为非零向量，如果对\(S\)中的每一个\(x\)，有\(\{ x + \lambda d \mid \lambda \ge 0 \} \subset S\)，则称\(d\)是\(S\)的方向。
设\(d^{(1)}\)和\(d^{(2)}\)是\(S\)的两个方向，若对任何正数\(\lambda\)，有\(d^{(1)} \neq \lambda d^{(2)}\)，则称\(d^{(1)}\)和\(d^{(2)}\)是两个不同的方向。
设\(S = \{ x \mid Ax = b, x \ge 0 \} \neq \emptyset\)，\(d\)是非零向量，则\(d\)是\(S\)的方向 \(\iff\) \(d \ge 0\)且\(Ad = 0\)。
极方向
若\(S\)的方向\(d\)不能表示成该集合的两个不同方向的正的线性组合，则称\(d\)为\(S\)的极方向。
例：设\(S = \{ (x_1, x_2)^T \mid x_2 \ge \lvert x_1 \rvert \}, d^{(1)} = (1, 1)^T, d^{(2)} = (-1, 1)^T\)，则\(d^{(1)}, d^{(2)}\)是\(S\)的极方向。
解：对\(\forall x \in S, \forall \lambda \ge 0\)，有
\(x + \lambda d^{(1)} = (x_1, x_2)^T + \lambda (1, 1)^T = (x_1 + \lambda, x_2 + \lambda)^T\)
\(x \in S \implies x_2 \ge \lvert x_1 \rvert\)
而\(x_2 + \lambda \ge \lvert x_1 \rvert + \lambda \ge \lvert x_1 + \lambda \rvert\)，
\(\implies \{ x + \lambda d^{(1)} \mid \lambda \ge 0 \} \subset S\)
故\(d^{(1)}\)是\(S\)的方向。
设\(d^{(1)} = \lambda_1 (x_1, x_2)^T + \lambda_2 (y_1, y_2)^T\)，其中\(\lambda_1, \lambda_2 \gt 0\), \((x_1, x_2)^T, (y_1, y_2)^T\)是\(S\)的方向，则有
\(\left\{ \begin{array}{c} 1 = \lambda_1 x_1 + \lambda_2 y_1 \\ 1 = \lambda_1 x_2 + \lambda_2 y_2 \end{array} \right. \implies \lambda_1 x_1 + \lambda_2 y_1 = \lambda_1 x_2 + \lambda_2 y_2\)
\(\implies x_1 = \frac{\lambda_2}{\lambda_1} (y_2 - y_1) + x_2\)
\((x_1, x_2)^T, (y_1, y_2)^T\)是\(S\)的方向，
\(\implies x_2 \ge \lvert x_1 \rvert, y_2 \ge \lvert y_1 \rvert, (x_1, x_2)^T \neq 0, (y_1, y_2)^T \neq 0\)
\(\implies x_2 \ge \lvert x_1 \rvert = \left \lvert \frac{\lambda_2}{\lambda_1} (y_2 - y_1) + x_2 \right \rvert \implies y_2 \le y_1\)
\(y_2 \ge \lvert y_1 \rvert \implies y_2 = y_1 \implies x_2 = x_1 \implies (x_1, x_2)^T = \frac{x_1}{y_1} (y_1, y_2)^T\)
故\(d^{(1)}\)是\(S\)的极方向。
多面集的表示定理
设\(S = \{ x \mid Ax = b, x \ge 0 \}\)为非空多面集，则有
极点集非空，且存在有限个极点\(x^{(1)}, \cdots, x^{(k)}\)
极方向集合为空集 \(\iff\) \(S\)有界。若\(S\)无界，则存在有限个极方向\(d^{(1)}, d^{(2)}, \cdots, d^{(l)}\)
\(x \in S \iff x = \sum_{j = 1}^k \lambda_j x^{(j)} + \sum_{j = 1}^l \mu_j d^{(j)}\)
其中\(\lambda_j \ge 0, j = 1, 2, \cdots, k, \sum_{j = 1}^k \lambda_j = 1\)
\(\mu_j \ge 0, j = 1, 2, \cdots, l\)
凸集分离定理
设\(S_1\)和\(S_2\)是\(E^n\)中两个非空集合，
\(H = \{ x \mid p^T x = \alpha \}\)为超平面，
如果对\(\forall x \in S_1\)，都有\(p^T x \ge \alpha\)，
对\(\forall x \in S_2\)，都有\(p^x \le \alpha\)，
则称超平面\(H\)分离集合\(S_1\)和\(S_2\)。
Farkas定理
设\(A\)为\(m \times n\)矩阵，\(c\)为\(n\)维列向量，
则\(Ax \le 0, c^T x \gt 0\)有解，
\(\iff\) \(A^T y = c, y \ge 0\)无解。
证：\(\implies\)
设存在\(y \ge 0\)，使得\(A^T y = c\)
则\(y^T A = c^T\)
设\(\overline{x}\)为\(Ax \le 0, c^T x \gt 0\)的一个解，
则有\(A \overline{x} \le 0, c^T \overline{x} \gt 0\)
\(\implies y^T A \overline{x} = c^T \overline{x} \gt 0 \quad (1)\)
\(y \ge 0, A \overline{x} \le 0 \implies y^T A \overline{x} \le 0\)与\((1)\)矛盾。
\(\impliedby\)
设\(A^T y = c, y \ge 0\)无解，令\(S = \{ z \mid z = A^T y, y \ge 0 \}\)，则\(c \notin S\)
可以证明\(S\)为闭凸集，由凸集分离定理知，
\(\exists x \neq 0, \varepsilon \gt 0\)，使得对
\(\forall z \in S\)，有\(x^T c \ge \varepsilon + x^T z\)
\(\varepsilon \gt 0 \implies x^T c \gt x^T z\)
\(\implies c^T x \gt z^T x = y^T Ax\)
即对任意的\(y \ge 0\)，有\(c^T x \gt y^T Ax \quad (2)\)
令\(y = 0\)，得\(c^T x \gt 0\)
\(c^T x\)为一定数，\(y\)的分量可取任意大
\(\implies\)由\((2)\)，必有\(Ax \le 0\)
故非零向量\(x\)是\(Ax \le 0, c^T x \gt 0\)的解。
例题
例：设\(A\)是\(m \times n\)矩阵，\(B\)是\(l \times n\)矩阵，\(c \in E^n\)，证明下列两个系统恰有一个有解：
系1 \(Ax \le 0, Bx = 0, c^T x \gt 0\)，对某些\(x \in E^n\)。
系2 \(A^T y + B^T z = c, y \ge 0\)，对某些\(y \in E^n\)和\(z \in E^l\)。
证：\(Bx = 0\) 等价于 \(\left\{ \begin{array}{c} Bx \le 0 \\ Bx \ge 0 \end{array} \right.\)
故系统1有解，即
\(\begin{bmatrix} A \\ B \\ -B \end{bmatrix} x \le 0, c^T x \gt 0\)有解。
由Farkas定理知，
\(\begin{pmatrix} A^T & B^T & -B^T \end{pmatrix} \begin{bmatrix} y \\ u \\ v \end{bmatrix} = c, \begin{bmatrix} y \\ u \\ v \end{bmatrix} \ge 0\)无解。
令\(z = u - v\)，则
\(A^T y + B^T z = c, y \ge 0\)无解。
即系统2无解。
反之，若系统2有解。即
\(\begin{pmatrix} A^T & B^T & -B^T \end{pmatrix} \begin{bmatrix} y \\ u \\ v \end{bmatrix} = c, \begin{bmatrix} y \\ u \\ v \end{bmatrix} \ge 0\)有解。
由Farkas定理，知
\(\begin{bmatrix} A \\ B \\ -B \end{bmatrix} x \le 0, c^T x \gt 0\)无解。
即\(Ax \le 0, Bx = 0, c^T x \gt 0\)无解，亦即系统1无解。
综上可得，两个系统恰有一个有解。
Gordan定理
设\(A\)为\(m \times n\)矩阵，
则\(Ax \lt 0\)有解，
\(\iff\) \(A^T y = 0, y \ge 0 (y \neq 0)\)无解。
证：\(\implies\)
设存在\(\overline{x}\)，使得\(A \overline{x} \lt 0\)
若存在非零向量\(y \ge 0\)，使得\(A^T y = 0\)
则有\(y^T A = 0\)，\(\implies y^T A \overline{x} = 0\)
\(A \overline{x} \lt 0 \implies\) \(y\)的各分量不可能为非负数，与\(y \ge 0\)矛盾。
\(\impliedby\)
（证等价命题）即若\(Ax \lt 0\)无解，则存在非零向量\(y \ge 0\)，使得\(A^T y = 0\)
设\(Ax \lt 0\)无解，令\(S_1 = \{ z \mid z = Ax, x \in E^n \}, S_2 = \{ z \mid z \lt 0 \}\)
\(Ax \lt 0\)无解 \(\implies\) \(S_1 \bigcap S_2 = \emptyset\)
由分离定理知，存在非零向量\(y\)，使得对\(\forall x \in E^n, \forall z \in S_2\)，有\(y^T Ax \ge y^T z \quad (1)\)
特别地，当\(x = 0\)时，有\(y^T z \le 0\)。
\(z \lt 0\)，它的分量可取任意负数 \(\implies\) \(y \ge 0\)
在\((1)\)中令\(z \to 0\)，则对\(\forall x \in E^n\)，有
\(y^T Ax \ge 0 \quad (2)\)
令\(x = -A^T y\)，代入\((2)\)，得\(-y^T A A^T y \ge 0\)
即\(-\lVert A^T y \rVert \ge 0\) \(\implies\) \(A^T y = 0\)
故存在非零向量\(y \ge 0\)，使得\(A^T y = 0\)
